package skiplist

import "math/rand"

/**
 * @Author : bothinli
 * @Description:
 */

type SkipList struct {
	head *Node
	cnt  int
}

type Node struct {
	nextNodes []*Node
	key       int
	value     interface{}
}

func New() *SkipList {
	return &SkipList{
		head: &Node{
			nextNodes: make([]*Node, 0),
		},
		cnt: 0,
	}
}

// Get
// @Description: 获取
// @receiver sl
// @param key int
// @return interface{}
// @return bool
func (sl *SkipList) Get(key int) (interface{}, bool) {
	if node := sl.search(key); node != nil {
		return node.value, true
	}

	return nil, false
}

func (sl *SkipList) search(key int) *Node {
	curNode := sl.head
	// 垂直索引 从高层索引出发
	for level := len(sl.head.nextNodes) - 1; level >= 0; level-- {

		// 同一层索引中搜索，如果当前节点的next小于搜索key，则一直往后移动
		for curNode.nextNodes[level] != nil && curNode.nextNodes[level].key < key {
			curNode = curNode.nextNodes[level]
		}

		// 如果当前节点不是head，那当前节点的key一定是小于搜索key，需要对比当前节点的next等于搜索key
		if curNode.nextNodes[level] != nil && curNode.nextNodes[level].key == key {
			return curNode.nextNodes[level]
		}

		// 下降高度
	}
	return nil
}

// Insert
// @Description: 插入
// @receiver sl
// @param key
// @param value
// @return bool
func (sl *SkipList) Insert(key int, value interface{}) bool {
	// 如果存在则直接更新
	if node := sl.search(key); node != nil {
		node.value = value
		return true
	}

	height := sl.getHeight()

	for len(sl.head.nextNodes)-1 < height {
		sl.head.nextNodes = append(sl.head.nextNodes, nil)
	}

	newNode := &Node{
		nextNodes: make([]*Node, height+1),
		key:       key,
		value:     value,
	}
	curNode := sl.head
	for level := height; level >= 0; level-- {
		for curNode.nextNodes[level] != nil && curNode.nextNodes[level].key < key {
			curNode = curNode.nextNodes[level]
		}

		newNode.nextNodes[level] = curNode.nextNodes[level]
		curNode.nextNodes[level] = newNode
	}

	sl.cnt++

	return true
}

func (sl *SkipList) getHeight() int {
	level := 0
	for rand.Int()%2 == 1 {
		level++
	}
	return level
}

// Delete
// @Description: 删除
// @receiver sl
// @param key
// @return bool
func (sl *SkipList) Delete(key int) bool {

	isDelete := false
	curNode := sl.head
	for level := len(sl.head.nextNodes) - 1; level >= 0; level-- {
		for curNode.nextNodes[level] != nil && curNode.nextNodes[level].key < key {
			curNode = curNode.nextNodes[level]
		}

		// 找到对应节点，移除当前层节点
		if curNode.nextNodes[level] != nil && curNode.nextNodes[level].key == key {
			var tmp = curNode.nextNodes[level]
			curNode.nextNodes[level] = curNode.nextNodes[level].nextNodes[level]
			tmp.nextNodes[level] = nil
			isDelete = true
		}
	}

	// 调整高度 若某层没有节点，则去除
	delLevel := 0
	for level := len(sl.head.nextNodes) - 1; level >= 0 && sl.head.nextNodes[level] == nil; level-- {
		delLevel++
	}
	sl.head.nextNodes = sl.head.nextNodes[:len(sl.head.nextNodes)-delLevel]

	sl.cnt--

	return isDelete
}

// Ceiling
// @Description: 获取大于等于key的最小值
// @receiver sl
// @param key
// @return interface{}
// @return bool
func (sl *SkipList) Ceiling(key int) (interface{}, bool) {
	if node := sl.ceiling(key); node != nil {
		return node.value, true
	}
	return nil, false
}

func (sl *SkipList) ceiling(key int) *Node {
	curNode := sl.head
	for level := len(sl.head.nextNodes) - 1; level >= 0; level-- {
		for curNode.nextNodes[level] != nil && curNode.nextNodes[level].key < key {
			curNode = curNode.nextNodes[level]
		}

		if curNode.nextNodes[level] != nil && curNode.nextNodes[level].key == key {
			return curNode.nextNodes[level]
		}

		if level == 0 {
			return curNode.nextNodes[level]
		}
	}
	return nil
}

// Range
// @Description: 获取区间值
// @receiver sl
// @param start
// @param end
// @return []interface{}
func (sl *SkipList) Range(start int, end int) []interface{} {
	if end < start {
		start, end = end, start
	}

	node := sl.ceiling(start)

	ans := make([]interface{}, 0)

	for node != nil && node.key < end {
		ans = append(ans, node.value)
		node = node.nextNodes[0]
	}
	return ans
}

// Floor
// @Description: 获取小于等于key的最大值
// @receiver sl
// @param key
// @return interface{}
// @return bool
func (sl *SkipList) Floor(key int) (interface{}, bool) {
	if node := sl.floor(key); node != nil {
		return node.value, true
	}
	return nil, false
}

func (sl *SkipList) floor(key int) *Node {
	curNode := sl.head

	for level := len(sl.head.nextNodes) - 1; level >= 0; level-- {
		for curNode.nextNodes[level] != nil && curNode.nextNodes[level].key < key {
			curNode = curNode.nextNodes[level]
		}

		if curNode.nextNodes[level] != nil && curNode.nextNodes[level].key == key {
			return curNode.nextNodes[level]
		}
	}

	return curNode
}

func (sl *SkipList) Len() int {
	return sl.cnt
}
